package binarysearchtree;

import binarytree.MyBinaryTree;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User:周次煜
 * Date: 2024-04-19
 * Time：23:39
 */


public class MyBinarySearchTree {
    public static class TreeNode {
        public int val;
        public TreeNode left;
        public TreeNode right;

        public TreeNode(int val) {
            this.val = val;
        }
    }

    public static TreeNode root;
    public  TreeNode search(int val) {
        if (isEmpty()) return null;
        TreeNode cur=root;
        while (cur != null) {
            if (cur.val < val) {
                cur=cur.right;
            } else if(cur.val > val) {
                cur=cur.left;
            } else {
                return cur;
            }
        }

        return  null;
    }

    public void insert(int val) {
        TreeNode node = new TreeNode(val);

        if (isEmpty()) {
            root=node;
            return;
        }


        TreeNode cur = root;
        TreeNode parent = null;
        while (cur != null) {
            parent=cur;
            if (cur.val < val) {
                cur=cur.right;
            } else if (cur.val > val) {
                cur=cur.left;
            } else {
                return;
            }
        }


        if (parent.val < val) {
            parent.right=node;
        } else {
            parent.left=node;
        }

    }

    private  boolean isEmpty() {
        return root==null;
    }


    public TreeNode remove(int val) {
        if (isEmpty()) return null;
        TreeNode cur =root;
        TreeNode parent=cur;
        while (cur != null) {

            if (cur.val < val) {
                parent=cur;
                cur=cur.right;
            } else if (cur.val > val) {
                parent=cur;
                cur=cur.left;
            } else  {
                removeFunc(cur,parent);
                break;
            }

        }

        return cur;
    }

    /**
     * 二叉搜索树的删除是需要分类
     * @param node
     * @param parent
     */
    private void removeFunc(TreeNode node,TreeNode parent) {

        if (node.left==null) {
            if (parent.left==node) {
                parent.left=node.right;
            } else if (parent.right==node) {
                parent.right=node.right;
            } else {
                parent=parent.right;
                root=parent;
            }
        } else if (node.right==null) {
            if (parent.left==node) {
                parent.left=node.left;
            } else if (parent.right==node) {
                parent.right=node.left;
            } else {
                parent=parent.left;
                root=parent;
            }
        } else {
            TreeNode cur=node.left;
            TreeNode curN=node;

            while (cur.right != null) {
                curN=cur;
                cur=cur.right;
            }
            node.val=cur.val;
            if (curN.left==cur) {
                curN.left=null;
                return;
            }

            curN.right=null;
        }

    }


    public void  inorder(TreeNode root) {
        if (root==null) {
            return;
        }
        inorder(root.left);
        System.out.print(root.val+" ");
        inorder(root.right);

    }








}
